# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# class Solution:
#     # 返回对应节点TreeNode
#     def KthNode(self, pRoot, k):
#         # write code here
#         # 先排序再找
#         if not pRoot:
#             return None
#         node_list = self.get_list(pRoot)
#         # print(node_list)
#
#         if k <= 0 or k > len(node_list):
#             return None
#         return node_list[k-1]
#     def get_list(self, root):
#         res = [root]
#         if root.left:
#             res = self.get_list(root.left) + res
#         if root.right:
#             res += self.get_list(root.right)
#         return res
class Solution:
    count = 0
    def KthNode(self, pRoot, k):
        '''
        这种写法只有在count == k时才会返回
        :param pRoot:
        :param k:
        :return:
        '''
        if not pRoot:
            return None
        node = self.KthNode(pRoot.left, k)
        if node:
            return node
        self.count += 1
        if self.count == k:
            return pRoot
        node = self.KthNode(pRoot.right, k)
        if node:
            return node


tree = TreeNode(8)
tree.left = TreeNode(6)
tree.right = TreeNode(10)
tree.left.left = TreeNode(5)
tree.left.right = TreeNode(7)
tree.right.left = TreeNode(9)
tree.right.right = TreeNode(11)
test = Solution()
print(test.KthNode(tree, 1))